package top.serms.leetcode;

import java.util.Arrays;

/**
 * @Author: SerMs
 * @Date: 2023/10/26 08 59
 * @Email: 1839928782@qq.com
 * @Blog: https://serms.top
 **/
public class LeetCode977_SortedSquares {


    public static void main(String[] args) {
        int[] nums = new int[]{-4, -1, 0, 3, 10};
        System.out.println(Arrays.toString(sortedSquares(nums)));
        System.out.println(Arrays.toString(sortedSquaresDPointer(nums)));
        System.out.println(Arrays.toString(sortedSquaresDPointerTwo(nums)));
    }

    public static int[] sortedSquaresDPointerTwo(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;pos--) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            } else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
        }
        return ans;
    }

    // 双指针解法
    public static int[] sortedSquaresDPointer(int[] nums) {
        // 初始化左指针为0，右指针为数组长度减1
        int left = 0;
        int right = nums.length - 1;
        // 新数组
        int[] result = new int[nums.length];
        // 初始化新数组的索引为数组长度减1
        int index = right;
        //  当左指针小于等于右指针时，进行循环
        while (left <= right) {
            // 如果左指针指向的数的平方大于右指针指向的数的平方，
            // 将左指针指向的数的平方插入到新数组的末尾，同时左指针向右移动一位
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[index--] = nums[left] * nums[left];
                left++;
            } else {
                // 如果右指针指向的数的平方大于左指针指向的数的平方，
                // 将右指针指向的数的平方插入到新数组的末尾，同时右指针向左移动一位
                result[index--] = nums[right] * nums[right];
                right--;
            }
        }
        // 循环之后新数组整体有序
        return result;
    }


    // 有序数组的平方根
    public static int[] sortedSquares(int[] nums) {
        int[] arry = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arry[i] = nums[i] * nums[i];
        }
//        arry = Arrays.stream(arry).boxed().sorted((b, a) -> b - a).mapToInt(Integer::intValue).toArray();
        Arrays.sort(arry);
        return arry;
    }
}
